package morris

import "math"

func GetMinHeight(head *Node) int {
	if head == nil {
		return 0
	}
	return GetMinHeightProcess(head)
}

func GetMinHeightProcess(node *Node) int {
	if node.Left == nil && node.Right == nil {
		return 1
	}
	leftHeight := math.MaxInt64
	if node.Left != nil {
		leftHeight = GetMinHeightProcess(node.Left)
	}
	rightHeight := math.MaxInt64
	if node.Left != nil {
		rightHeight = GetMinHeightProcess(node.Left)
	}
	return 1 + Min(leftHeight, rightHeight)
}

func Min(a, b int ) int {
	if a > b {
		return b
	}
	return a
}

func MorrisGetMinHeight(head *Node) int {

	minHeight := math.MaxInt64
	var rightBoardNum int
	var curLevel int

	cur := head
	for cur != nil {
		mostRight := cur.Left
		if mostRight != nil {
			rightBoardNum = 1
			for mostRight.Right != nil && mostRight.Right != cur {
				rightBoardNum++
				mostRight = mostRight.Right
			}
			if mostRight.Right == nil {
				mostRight.Right = cur
				cur = cur.Left
				curLevel++
				continue
			} else {
				if mostRight.Left == nil {
					minHeight = Min(minHeight, curLevel)
					curLevel -= rightBoardNum
				}
				mostRight.Right = nil
			}
		} else {
			curLevel++
		}
		cur = cur.Right
	}
	return minHeight
}